package algorithm_demo.demo01;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 用双链表实现双端队列
 *
 * 双端队列（头部和尾部增加Node节点）
 *
 * @author Api
 * @date 2023/1/27 22:50
 */
public class Code17_DoubleLinkedListToDeQueue {
    public static class Node<V>{
        private V value;
        private Node<V> last;//上一个节点
        private Node<V> next;//下一个节点
        public Node(V value){
            this.value = value;
            this.last = null;
            this.next = null;
        }
    }

    public static class MyDeque<V>{
        private Node<V> head;
        private Node<V> tail;
        private int size;
        public MyDeque(){
            this.head = null;
            this.tail = null;
            this.size = 0;
        }

        public boolean isEmpty(){
            return size == 0;
        }

        public int size(){
            return size;
        }
        //在双向链表中头部增加一个元素。
        public void pushHead(V value){
            Node<V> cur = new Node<>(value);
            if (head==null){//head为null时，表示无元素，头和尾均指向自己
                head = cur;
                tail = cur;
            }else{
                cur.next = head;
                head.last = cur;
                head = cur;
            }
            size++;
        }
        //在双向链表中尾部增加一个元素。
        public void pushTail(V value){
            Node<V> cur = new Node<V>(value);
            if (tail == null){
                head = cur;
                tail = cur;
            }else{
                tail.next = cur;
                cur.last = tail;
                tail = cur;
            }
            size++;
        }
        //双向链表头部弹出一个元素
        public V pollHead(){
            V ans = null;
            if (head == null){
                return ans;
            }
            size--;
            ans = head.value;
            if (head == tail){
                head = null;
                tail = null;
            }else{
                head = head.next;
                head.last = null;
            }
            return ans;
        }
        //双向链表尾部弹出一个元素
        public V pollTail(){
            V ans = null;
            if (head == null){
                return ans;
            }
            size--;
            ans = tail.value;
            if (head == tail) {
                head = null;
                tail = null;
            }else{
                tail = tail.last;
                tail.next = null;
            }
            return ans;

        }

        //查看头部元素
        public V peekHead(){
            V ans = null;
            if (head != null){
                ans = head.value;
            }
            return ans;
        }


        //查看尾部元素
        public V peekTail(){
            V ans = null;
            if (tail != null){
                ans = tail.value;
            }
            return ans;
        }
    }

    public static void testDeque() {
        MyDeque<Integer> myDeque = new MyDeque<>();
        Deque<Integer> test = new LinkedList<>();
        int testTimes = 5000000;
        int maxValue = 200000000;
        System.out.println("测试开始！");
        for(int i = 0; i< testTimes; i++){
            if (myDeque.isEmpty() != test.isEmpty()){
                System.out.println("Oops!");
            }
            if (myDeque.size != test.size()){
                System.out.println("Oops!");
            }
            double decide = Math.random();
            if (decide <0.33){
                int num = (int)(Math.random()*maxValue);
                if (Math.random()<0.5){
                    myDeque.pushHead(num);
                    test.addFirst(num);
                }else{
                    myDeque.pushTail(num);
                    test.addLast(num);
                }
            }else if(decide < 0.66){
                if (!myDeque.isEmpty()){
                    int num1 = 0;
                    int num2 = 0;
                    if (Math.random()<0.5){
                        num1 = myDeque.pollHead();
                        num2 = test.pollFirst();
                    }else{
                        num1 = myDeque.pollTail();
                        num2 = test.pollLast();
                    }
                    if (num1 != num2){
                        System.out.println("Oops!");
                    }
                }
            }else{
                if (!myDeque.isEmpty()){
                    int num1 = 0;
                    int num2 = 0;
                    if (Math.random()<0.5){
                        num1 = myDeque.peekHead();
                        num2 = test.peekFirst();
                    }else{
                        num1 = myDeque.peekTail();
                        num2 = test.peekLast();
                    }
                    if (num1 != num2){
                        System.out.println("Oops!");
                    }
                }
            }
        }

        if (myDeque.size() != test.size()){
            System.out.println("Oops!");
        }
        while(!myDeque.isEmpty()){
            int num1 = myDeque.pollHead();
            int num2 = test.pollFirst();
            if (num1 != num2){
                System.out.println("Oops!");
            }
        }
        System.out.println("测试结束！");
    }

    public static void main(String[] args){
        testDeque();
    }
}
